1. Field of the Invention
The present invention relates to techniques for performing interval computations within computer systems. More specifically, the present invention relates to a method and an apparatus for solving a parametric multi-objective optimization problem in a combined design space and parameter space using interval techniques within a computer system.
2. Related Art
In many real-world optimization problems, there are often several objectives that one would like to optimize. In such cases, rarely do the optima of each objective coincide. Hence, one is left with tradeoffs between the individual objectives that must be incorporated in the solution. The goal of multi-objective optimization is then to determine a set of points that describe the optimal trade-offs between objectives.
An example of multi-objective optimization is that of minimizing price and maximizing performance. A common metric associated with these two objectives is the price-performance ratio. This number, however, oversimplifies the optimization problem. This oversimplification lies in the implicit assumption that a unit of price is equal to a unit of performance, which in general is not the case. For example, a college freshman and a national lab would most likely weight these two objectives differently when purchasing a computer. A more insightful approach to the problem is depicted in FIG. 1, which shows the price and runtime (inverse performance) of a set of points representing (fictitious) computers. Expressed in this manner, one would like to minimize each objective.
Unfortunately, minimizing both objectives simultaneously is generally not possible, and is not the case in this example. The best one can do is come up with an optimal trade-off. This trade-off is optimal in the sense that it is not possible to improve one objective without degrading at least one other objective. The filled circles in FIG. 1 are points which exhibit this optimal trade-off between the multiple objectives, which comprise the “Pareto front.” Obtaining the Pareto front is one of the goals of multi-objective optimization, both in identifying optimal points and in providing a sensitivity analysis. This sensitivity analysis considers the shape of the Pareto front. Convex portions of the Pareto front (points which lie on the convex hull of all points) indicate an ability to satisfy all objectives relative to regions of the Pareto front which are non-convex (the “indented” region of Pareto front in FIG. 1).
In addition to determining the Pareto front, another goal of multi-objective optimization is to identify values of the objective functions' independent variables which are mapped to points on the Pareto front. In our example, processor speed, memory, system architecture, etc., are all independent variables (perhaps constrained) of both price and performance objective functions. One would like to know which sets of these independent variables map to points on the Pareto front. Such sets are termed “Pareto optimal sets.”
Previously, we have proposed using interval techniques to solve multi-objective optimization problems (see “Method and Apparatus for Using Interval Techniques to Solve a Multi-objective Optimization Problem,” with patent application Ser. No. 10/691,868, and filing date Oct. 22, 2003 by the same inventor as the present application; and the related patent, currently issued as U.S. Pat. No. 7,295,956 on Oct. 24, 2007).
Note that these previous interval techniques capture all points on a Pareto front in the objective space, as well as the corresponding points of a Pareto optimal set in the design space. However, these techniques were specifically designed to solve the type of multi-objective optimization problems which depend exclusively on “design-space variables,” which have fixed values once a particular design is chosen. However, in real-world design-optimization problems, there exists another type of multi-objective optimization problem where the objective functions depend on both the design-space variables and “parameters,” which are variables that can be modified after a particular design is chosen. These types of design-optimization problems are referred to as “parametric multi-objective optimization problems,” while the previous multi-objective optimization problems can be analogously referred to as “nonparametric multi-objective optimization problems.” While both types of multi-objective optimization problems have important real-world applications, the parametric problems are typically significantly more complicated to solve, and hence have not been widely studied. We now illustrate this type of problems with the following example: an optimal airfoil design.
While aerodynamic shape optimization is a very complicated design problem with many objectives and constraints, we will look at a simplified case. We are concerned with two objective functions: minimizing the aerodynamic drag and maximizing the lift of the airfoil. Note that both of these objectives are functions of many variables related to the geometry of the airfoil. Most of these variables will be fixed for a particular design, such as the camber, length and thickness of the airfoil. Such variables are the aforementioned design-space variables.
However, some quantities, such as aileron or flap angle, can be modified after a design is selected, hence are not fixed once the design is chosen. We refer to these quantities as “parameters” instead of the design-space variables. Note that a parameter can take on a range of values during operation of a chosen design, hence a parameter is also referred to as an “operational variable.” For example, the flap angle of the airfoil can be adjusted to different positions for optimal flight conditions during different stages of a flight operation. The question is then how to take into account these parameters such the flap angle into the design-optimization process.
One approach would be simply treat these parameters as some other design variables, and subsequently determine the Pareto front over the entire design space. At the other end of the spectrum, one could determine the Pareto front for a particular set, or sets, of parameters individually. Unfortunately, both of these approaches are flawed: the latter approach significantly undermines the effectiveness of multi-objective optimization; and the former approach fails to leverage the operational variability of some parameters when Pareto fronts are used to select designs.
Hence, what is needed is a technique for solving parametric multi-objective optimization problems which distinguishes between design-space variables and parameters without the above-described problems.